# -*- coding:utf-8 -*-

import random

# A = [69, 62, 89, 37, 97, 17, 28, 49]
A = [69, 62, 89, 77, 97, 17, 28, 49] 

print(type(A))


def quicksort(l:list, left, right):
    """快速排序
    """
    if(left >= right):
        return
    
    pivot = l[random.randint(left, right)]

    ltemp = left
    rtemp = right

    while(ltemp < rtemp):
        while(ltemp < rtemp and l[ltemp] < pivot):
            ltemp += 1
        while(ltemp < rtemp and l[rtemp] > pivot):
            rtemp -= 1
        
        if(ltemp < rtemp):
            temp = l[ltemp]
            l[ltemp] = l[rtemp]
            l[rtemp] = temp

    quicksort(l, left, ltemp-1)
    quicksort(l, ltemp+1, right)

def heapsort(l:list):

    size = len(l)

    if(size < 2):
        return
    
    # 构造大顶堆
    for i in range(size // 2 - 1, -1, -1):
        heapify(l, i, size)
    # 排序
    for i in range(size - 1, 0, -1):
        swap(l, 0, i)
        size -= 1
        heapify(l, 0, size)


def heapify(l:list, parent, size):
    
    # 子左节点
    child = 2 * parent + 1
    # 判断是否存在左子节点
    if(child >= size):
        return

    if(child + 1 < size and l[child] < l[child + 1]):
        child += 1
    
    if(l[child] > l[parent]):
        swap(l, parent, child)
        # 交换后，调整这个子节点的子节点
        heapify(l, child, size)

def shellsort(l:list):
    size = len(l)
    if(size < 2):
        return
    
    # Shell增量序列的取法D[M]=⌊N/2⌋,Dk=⌊Dk+1/2⌋：1，2，4，8，...
    gap = size >> 1
    # Hibbard增量序列的取法为D[k]=2^k − 1：1, 3, 7, 15, ...
    # Sedgewick增量序列的取法为D[i]=9∗4^i−9∗2^i+1或4^i−3∗2^i+1：{1, 5, 19, 41, 109, 209, 505, 929, 2161...}

    while gap > 0:
        for i in range(gap, size):
            temp = l[i]
            j = i -gap 
            while(j >= 0 and temp < l[j]):
                l[j + gap] = l[j]
                j -= gap
            l[j + gap] = temp
            print(l)
        gap = gap >> 1

def megresort(l:list):
    n = len(l)

    if(n < 2):
        return
    t = [1] * n

    sort(l, t, 0, n - 1)

def sort(l:list, t:list, left, right):
    if (left == right):
        return
    mid = left + ((right - left) >> 1)
    sort(l, t, left, mid)
    sort(l, t, mid + 1, right)
    megre(l, t, left, right, mid)

def megre(l:list, t:list, left, right, mid):
    i = left # 左序列起始指针
    j = mid + 1 # 右序列起始指针
    k = left # 临时序列起始指针

    while(i <= mid and j <= right):
        if(l[i] < l[j]):
            t[k] = l[i]
            i += 1
            k += 1
        else:
            t[k] = l[j]
            j += 1
            k += 1
    while(i <= mid):
        t[k] = l[i]
        i += 1
        k += 1
    while(j <= right):
        t[k] = l[j]
        j += 1
        k += 1

    for m in range(left, right + 1):
        l[m] = t[m]
    print(l)

def swap(l:list, i, j):
    temp = l[i]
    l[i] = l[j]
    l[j] = temp

if __name__ == "__main__":
    # quicksort(A, 0, len(A)-1)
    # heapsort(A)
    # shellsort(A)
    megresort(A)
    print(A)